GATE CSE 2006
Q31.
The following functional dependencies are given: AB\rightarrow CD,AF\rightarrow D,DE\rightarrow F,C\rightarrow G,F\rightarrow E,G\rightarrow A Which one of the following options is false?Q32.
For S \in (0+1)^{*}, let d(s) denote the decimal value of s (e.g. d(101)=5). Let L={s \in (0+1)*| d(s) mod 5=2 and d(s) mod 7\neq4} Which one of the following statements is true?Q33.
A relation R is defined on ordered pairs of integers as follows: (x,y)R(u,v) if x\ltu and y\gtv. Then R isQ34.
A set X can be represented by an array x[n] as follows x[i]=\left\{\begin{matrix} 1 &if i\in X \\ 0& otherwise \end{matrix}\right. Consider the following algorithm in which x,y and z are boolean arrays of size n; algorithm zzz(x[] , y[], z []) { int i; for (i=O; i < n; ++i) z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i]) } The set Z computed by the algorithm isQ35.
Given a set of elements N = {1,2,...,n} and two arbitrary subsets A\subseteqN and B\subseteqN , how many of the n! permutations p from N to N satisfy min[p(A)]=min[p(B)], where min(S) is the smallest integer in the set of integers S and p(S) is the set of integers obtained by applying permutation p to each element of S ?Q36.
We are given a set X=\{x_{1},...,x_{n}\} where x_{i}=2^{i}. A sample S\subseteq X is drawn by selecting each x_{i} independently with probability p_{i}=\frac{1}{2}. The expected value of the smallest number in sample S is:Q37.
Let S={1,2,3....,m},m \gt 3. Let X_{1},...,X_{n} be subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f(i) is the number of sets X_{j} that contain the element i. That is f(i)=|\{j|i\in X_{j}\}|. Then \sum_{i=1}^{m}f(i)Q38.
Let E,F and G be finite sets. Let X=(E \capF) - (F\capG) and Y = (E - (E\capG)) - (E - F). Which one of the following is true?Q39.
Let X, Y, Z be sets of sizes x, y and z respectively. Let W=X\timesY and E be the set of all subsets of W. The number of functions from Z to E isQ40.
The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?